package trees;

import java.util.ArrayList;
import java.util.List;

public class BinarySearchTree<T extends Comparable<T>> implements Tree<T> {

	private BSTNode<T> root;

	public BinarySearchTree() {

	}

	@Override
	public boolean insert(T val) {
		if (root == null) {
			root = new BSTNode<T>(val);
			return true;
		} else {
			if (search(val) != null)
				return false;

			return insert(root, val);
		}
	}

	private boolean insert(BSTNode<T> node, T val) {
		if (node.getVal().compareTo(val) > 0) {
			if (node.getLeft() == null) {
				BSTNode<T> newNode = new BSTNode<T>(val);
				node.setLeft(newNode);
				return true;
			} else
				return insert(node.getLeft(), val);
		} else if (node.getVal().compareTo(val) < 0) {
			if (node.getRight() == null) {
				BSTNode<T> newNode = new BSTNode<T>(val);
				node.setRight(newNode);
				return true;
			} else
				return insert(node.getRight(), val);
		}

		return false;
	}

	@Override
	public Node<T> delete(T val) {
		return delete(val, (BSTNode<T>) getRoot());
		// if (search(val) == null)
		// return null;
		//
		// BSTNode<T>[] nodes = search((BSTNode<T>) getRoot(), null, val);
		// BSTNode<T> parent = nodes[1], node = nodes[0];
		//
		// if (node.isLeaf()) {
		// if (parent == null)
		// root = null;
		// else if (parent.getLeft().equals(node))
		// parent.setLeft(null);
		// else if (parent.getRight().equals(node))
		// parent.setRight(null);
		// } else {
		// BSTNode<T> sub = null;
		// if (node.getLeft() != null) {
		// sub = removeMax(node.getLeft(), node);
		// } else {
		// sub = removeMin(node.getRight(), node);
		// }
		//
		// node.setVal(sub.getVal());
		// }
		//
		// return node;
	}

	private BSTNode<T> delete(T val, BSTNode<T> node) {
		if (node == null)
			return node;
		if (node.getVal().compareTo(val) > 0)
			node.setLeft(delete(val, node.getLeft()));
		else if (node.getVal().compareTo(val) < 0)
			node.setRight(delete(val, node.getRight()));
		else if (node.getLeft() != null && node.getRight() != null) {
			node.setVal(findMin(node.getRight()).getVal());
			node.setRight(delete(node.getVal(), node.getRight()));
		} else {
			if (node.equals(getRoot()))
				root = (node.getLeft() != null) ? node.getLeft() : node
						.getRight();
			else
				node = (node.getLeft() != null) ? node.getLeft() : node
						.getRight();
		}
		return node;
	}

	private BSTNode<T> findMin(BSTNode<T> node) {
		if (node == null)
			return null;
		else if (node.getLeft() == null)
			return node;
		else
			return findMin(node.getLeft());
	}

	@SuppressWarnings("unused")
	private BSTNode<T> removeMax(BSTNode<T> node, BSTNode<T> parent) {
		if (node.getRight() == null) {
			if (node.equals(parent.getLeft()))
				parent.setLeft(node.getLeft());
			else if (node.equals(parent.getRight()))
				parent.setRight(node.getLeft());
			return node;
		} else
			return removeMax(node.getRight(), node);
	}

	@SuppressWarnings("unused")
	private BSTNode<T> removeMin(BSTNode<T> node, BSTNode<T> parent) {
		if (node.getLeft() == null) {
			if (node.equals(parent.getLeft()))
				parent.setLeft(node.getRight());
			else if (node.equals(parent.getRight()))
				parent.setRight(node.getRight());
			return node;
		} else
			return removeMin(node.getLeft(), node);
	}

	@SuppressWarnings({ "unchecked", "unused" })
	private BSTNode<T>[] search(BSTNode<T> node, BSTNode<T> parent, T val) {
		if (node == null)
			return null;

		if (node.getVal().equals(val)) {
			return new BSTNode[] { node, parent };
		} else if (node.getVal().compareTo(val) > 0)
			return search(node.getLeft(), node, val);
		else
			return search(node.getRight(), node, val);
	}

	@Override
	public Node<T> search(T val) {

		return search((BSTNode<T>) getRoot(), val);
	}

	private Node<T> search(BSTNode<T> node, T val) {
		if (node == null)
			return null;

		if (node.getVal().equals(val))
			return node;
		else if (node.getVal().compareTo(val) > 0)
			return search(node.getLeft(), val);
		else
			return search(node.getRight(), val);
	}

	public List<Node<T>> inorderTraverse() {
		return inorderTraverse((BSTNode<T>) getRoot());
	}

	private List<Node<T>> inorderTraverse(BSTNode<T> root) {
		if (root == null)
			return null;

		List<Node<T>> leftList = inorderTraverse(root.getLeft());
		if (leftList == null)
			leftList = new ArrayList<Node<T>>();
		leftList.add(root);

		List<Node<T>> rightList = inorderTraverse(root.getRight());
		if (rightList != null)
			leftList.addAll(rightList);

		return leftList;
	}

	public List<Node<T>> preorderTraverse() {
		List<Node<T>> list = new ArrayList<Node<T>>();
		preorderTraverse((BSTNode<T>) getRoot(), list);
		return list;
	}

	private void preorderTraverse(BSTNode<T> node, List<Node<T>> list) {
		if (node != null) {
			list.add(node);
			preorderTraverse(node.getLeft(), list);
			preorderTraverse(node.getRight(), list);
		}
	}

	@Override
	public Node<T> getRoot() {
		return root;
	}

	@Override
	public List<Node<T>> postorderTraverse() {
		return postorderTraverse((BSTNode<T>) getRoot());
	}

	private List<Node<T>> postorderTraverse(BSTNode<T> node) {
		if (node == null)
			return new ArrayList<Node<T>>();

		List<Node<T>> list = postorderTraverse(node.getLeft());
		list.addAll(postorderTraverse(node.getRight()));
		list.add(node);

		return list;
	}

	public BSTNode<T> findNearest(BSTNode<T> root, T k) {
		if (root == null)
			throw new RuntimeException();

		return findNearest(root, k, null);
	}

	private BSTNode<T> findNearest(BSTNode<T> node, T k, BSTNode<T> n) {
		if (node == null)
			return n;

		if (node.getVal() == k)
			return node;
		else if (node.getVal().compareTo(k) > 0) {
			if (n == null)
				return findNearest(node.getLeft(), k, node);
			else
				return findNearest(node.getLeft(), k,
						Math.abs(node.getVal().compareTo(k)) < Math.abs(n
								.getVal().compareTo(k)) ? node : n);
		} else {
			if (n == null)
				return findNearest(node.getRight(), k, node);
			else
				return findNearest(node.getRight(), k,
						Math.abs(node.getVal().compareTo(k)) < Math.abs(n
								.getVal().compareTo(k)) ? node : n);
		}

	}
}
